公交路线(Leetcode 815)

题目分析

   最近的每日一题全部都是BFS，总是给小伙伴们介绍这类题型，可能会感觉到厌倦，但是集中训练也是非常有帮助的，而且最近这几题每一题的难度都较大，能做出这几道题目，有一种五岳归来不看山，黄山归来不看岳的感觉。

广度优先搜索

BFS的代码非常简单，有公式模板可以去套用，简而言之就是建立一个队列，从队头去状态，从队尾加状态。
本题的难点在于如何进行状态的抽象与表示，假设当前处于第k个车站，那么乘坐该站台的所有公交线路，假设该站台有m个公交线路，那么一次乘坐可以到达哪些站呢？想通这个问题，本题的状态表示就迎刃而解了。
答案是一次乘坐可以到达这些所有公交线路经过的所有站点。假设可以有m1和m2两个线路经过当前车站，m1线路经过k11、k12、k13这三个站点，m2路线经过k21、k22、k23、k24这四个站点，那么一次乘坐公交，可以乘坐m1线路到达三个站点，也可以乘坐m2线路到达四个站点。

所以我们需要知道某个站点的所有线路，但是输入的route是线路经过的所有站点，因此要建立一个哈希表，键为站点号，值为一个set集合，存放该站点可以乘坐的所有线路。

并建立两个set集合，分别表示已访问的站点和已访问的路线，当站点或路线已经访问，则不添加到队列进行剪枝。

当然本题从起始公交站搜索到终止公交站等价于从终止公交站搜索到起始公交站，因此可以使用双向BFS进行优化。

算法的**时间复杂度为$O(m^n)$，空间复杂度为$O(m^n)$**，其中m为线路个数，n站点个数。

下面是C++语言的题解

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) { return 0; }
        unordered_map<int, unordered_set<int>> dic;
        for (int i = 0; i < routes.size(); i++) { for (int x : routes[i]) { dic[x].insert(i); } }
        deque<int> beginQueue = { source };
        unordered_set<int> beginStationVisited = { source };
        deque<int> endQueue = { target };
        unordered_set<int> endStationVisited = { target };
        unordered_set<int> beginRouteIndexVisited = { };
        unordered_set<int> endRouteIndexVisited = { };
        int res = 0;
        while (true) {
            res++;
            int beginSize = beginQueue.size();
            while (beginSize-- > 0) {
                int curStation = beginQueue.front();
                beginQueue.pop_front();
                for (int route : dic[curStation]) {
                    if (!beginRouteIndexVisited.count(route)) {
                        beginRouteIndexVisited.insert(route);
                        for (int station : routes[route]) {
                            if (!beginStationVisited.count(station)) {
                                if (endStationVisited.count(station)) { return res; }
                                beginQueue.push_back(station);
                                beginStationVisited.insert(station);
                            }
                        }
                    }
                }
            }
            if (beginQueue.empty()) { return -1; }
            res++;
            int endSize = endQueue.size();
            while (endSize-- > 0) {
                int curStation = endQueue.front();
                endQueue.pop_front();
                for (int route : dic[curStation]) {
                    if (!endRouteIndexVisited.count(route)) { 
                        endRouteIndexVisited.insert(route);
                        for (int station : routes[route]) {
                            if (!endStationVisited.count(station)) {
                                if (beginStationVisited.count(station)) { return res; }
                                endQueue.push_back(station);
                                endStationVisited.insert(station);
                            }
                        }
                    }
                }
            }
            if (endQueue.empty()) { return -1; }
        }
    }
};

下面是Python语言的题解

class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0
        dic = {}
        for i in range(len(routes)):
            for x in routes[i]:
                lst = dic.setdefault(x, set())
                lst.add(i)
                dic[x] = lst
        begin_queue = deque([source])
        end_queue = deque([target])
        begin_station_visited = {source}
        end_station_visited = {target}
        begin_route_visited = set()
        end_route_visited = set()
        res = 0
        while True:
            res += 1
            begin_size = len(begin_queue)
            for _ in range(begin_size):
                cur_station = begin_queue.popleft()
                if cur_station in dic:
                    for route in dic[cur_station]:
                        if route not in begin_route_visited:
                            begin_route_visited.add(route)
                            for station in routes[route]:
                                if station not in begin_station_visited:
                                    if station in end_station_visited:
                                        return res
                                    begin_queue.append(station)
                                    begin_station_visited.add(station)
            if len(begin_queue) == 0:
                return -1
            res += 1
            end_size = len(end_queue)
            for _ in range(end_size):
                cur_station = end_queue.popleft()
                if cur_station in dic:
                    for route in dic[cur_station]:
                        if route not in end_route_visited:
                            end_route_visited.add(route)
                            for station in routes[route]:
                                if station not in end_station_visited:
                                    if station in begin_station_visited:
                                        return res
                                    end_queue.append(station)
                                    end_station_visited.add(station)
            if len(end_queue) == 0:
                return -1

对比C++和Python两种语言，可以发现C++语言中，创建数据结构时，会默认创建内层的数据，如vector a(10);等价于vector a(10, 0); vector<vector> a(10);等价于vector a(10, vector());因此可以直接进行push_back()，如a[0].push_back();哈希表同理，unordered_map<int, vector> a，此时可以直接写a[0].push_back(x)，因为哈希表中每一个元素都是vector类型，会调用其默认的构造函数。而在Java、Python语言中，则必须新建一个内层数据，才可以添加元素，如Java中要写ArrayList list = a.getOrDefault(0, new ArrayList()); list.add(x); a.put(0, list);在Python中要写lst = a.setdefault(0, list()) lst.append(x)。这是本题发现两种语言的主要差异

刷题总结

  听过上面的分析后，小伙伴能否自己实现BFS呢，一定要多刷多练，慢慢就会找到做题的感觉。